Round Overview
Discuss this match
SquareFreeString
Problem Details
Just check all substrings and check if they are a square. Here are implementations in a variety of languages:
Python
1
2
3
class SquareFreeString():
def isSquareFree(self, s):
return any((lambda w: len(w) % 2 == 0 and w[: len(w) / 2] == w[len(w) / 2: ])(s[i: i + j]) for j in range(1, len(s) + 1) for i in range(len(s) - j + 1)) * "not " + "square-free"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
bool check(string s) {
if (s.length() == 0 || s.length() % 2 == 1) return false;
for (int i = 0; i < s.length() / 2; i++) {
if (s[i] != s[i + s.length() / 2]) {
return false;
}
}
return true;
}
class SquareFreeString {
public: string isSquareFree(string s) {
for (int i = 0; i < s.length(); i++) {
string now = "";
for (int j = i; j < s.length(); j++) {
now += s[j];
if (check(now)) {
return "not square-free";
}
}
}
return "square-free";
}
};
</map> < /cmath></vector > </string> < /cstring></iomanip > </iostream> < /algorithm></unordered_map >
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
public class SquareFreeString {
static final int MAX_LEN = 50;
public static String isSquareFree(String s) {
int n = s.length();
for (int i = 0; i < n; ++i)
for (int k = 1; i + 2 * k <= n; ++k)
if (s.substring(i, i + k)
.equals(s.substring(i + k, i + 2 * k)))
return "not square-free";
return "square-free";
}
};
Consider the sorted array b of elements in a in order. We definitely need to choose indices i such that b[i] != a[i]. These also happen to be sufficient. So, our solution just needs to count the number of elements where b[i] != a[i].
Python
1 2 3 4
class SortingSubsets(): def getMinimalSize(self, a): return sum(x != y for x, y in zip(a, sorted(a)))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
using namespace std;
class SortingSubsets {
public: int getMinimalSize(vector < int > a) {
vector < int > b = a;
sort(b.begin(), b.end());
int ret = 0;
for (int i = 0; i < a.size(); i++) {
ret += (a[i] != b[i]);
}
return ret;
}
};
</int> < /int></algorithm > </iostream>
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
public class SortingSubsets {
public static int getMinimalSize(int[] a) {
int n = a.length;
int[] b = new int[n];
for (int i = 0; i < n; ++i)
b[i] = a[i];
Arrays.sort(b);
int ans = n;
for (int i = 0; i < n; ++i)
if (a[i] == b[i])
--ans;
return ans;
}
};
This is a classic game theory question. For each number, we can denote it as a “winning” number if the first player wins, and a “losing” number otherwise. Winning numbers and losing numbers can be defined recursively. Namely, a number is winning if and only there exists a losing number that it can reach. For our base cases, we can define numbers with an odd number of bits to be “winning”, so those that move onto that number can’t use it as a valid move. Thus, it suffices to keep track of the last m numbers on whether or not they are winning or losing. Note that the naive implementation may be a bit slow, so we should speed it up using bit masks for O(n) operations rather than O(nm). Here are some different implementations.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class ThueMorseGame {
public static String get(int n, int m) {
long full = (1 l << m) - 1;
long mask = full;
for (int i = 0; i <= n; ++i) {
int win;
if (Integer.bitCount(i) % 2 == 1 || mask != full)
win = 1;
else
win = 0;
mask = ((mask << 1) | win) & full;
assert 0 <= mask;
assert mask <= full;
}
return (mask & 1) == 1 ? "Alice" : "Bob";
}
};
1
2
3
4
5
6
7
8
9
10
11
public class ThueMorseGame {
public String get(int n, int m) {
if (n == 0) return "Bob";
long mask = 0;
for (int i = 0; i <= n; i++) {
int xx = Integer.bitCount(i) % 2;
mask = (((1 - xx) & (mask == 0 ? 1 L : 0 L)) << (long)(m - 1)) | (mask >> 1);
}
return ((mask >> (m - 1)) == 1) ? "Bob" : "Alice";
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
int popcount[1 << 16];
class ThueMorseGame {
public: string get(int n, int m) {
for (int i = 0; i < (1 << 16); i++) {
popcount[i] = __builtin_popcount(i);
}
unsigned long long state = (1 LL << m) - 1;
unsigned long long mask = (1 LL << m) - 1;
state--;
int maxv = 0;
for (int i = 1; i <= n; i++) {
int cur = false;
if ((popcount[i & 65535] + popcount[i >> 16]) % 2 == 1) {
cur = true;
} else {
if ((state & mask) != mask) {
cur = true;
}
}
state = (state << 1) | cur;
if (state % 2 == 0) maxv = i;
}
cout << maxv << " " << m << endl;
return (state % 2 == 0 ? "Bob" : "Alice");
}
};
</map> < /cmath></vector > </string> < /cstring></iomanip > </iostream> < /algorithm></unordered_map >
We can still define winning/losing numbers, but we also need to track whose turn is next. Thus, we only need to keep track of 10 numbers. After, we can use exponentiation to find the answer, or we can find the cycle length explicitly also since the cycle length is at most 2^10.
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class PartisanGame():
def getWinner(self, n, a, b):
a = list(a)
b = list(b)
if n == 0: return "Bob"
MAXK = 5
lw = (1 << (MAXK << 1))
def getNext(mask):
amask = mask >> MAXK
bmask = mask & ((1 << MAXK) - 1)
wina = not all(bmask & (1 << (MAXK - w)) for w in a)
winb = not all(amask & (1 << (MAXK - w)) for w in b)
amask = (amask >> 1) | (wina << (MAXK - 1))
bmask = (bmask >> 1) | (winb << (MAXK - 1))
return (amask << MAXK) | bmask
def mult(p, q):
return [p[q[i]]
for i in xrange(lw)]
perm = [getNext(i) for i in xrange(lw)]
ret = [i
for i in xrange(lw)]
n += 1
while n > 0:
if n % 2 == 1:
ret = mult(ret, perm)
perm = mult(perm, perm)
n >>= 1
return (ret[lw - 1] >> (2 * MAXK - 1)) * "Alice"
or "Bob"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
int maskToIdx[1000001];
int alice[1000001];
int bob[1000001];
class PartisanGame {
public: string getWinner(int n, vector < int > a, vector < int > b) {
memset(maskToIdx, 0, sizeof(maskToIdx));
alice[0] = false;
bob[0] = false;
for (int i = 1; i <= n; i++) {
alice[i] = false;
bob[i] = false;
for (int j = 0; j < a.size(); j++) {
if (a[j] <= i && !bob[i - a[j]]) {
alice[i] = true;
}
}
for (int j = 0; j < b.size(); j++) {
if (b[j] <= i && !alice[i - b[j]]) {
bob[i] = true;
}
}
if (i > 100) {
int curMask = 0;
for (int j = 0; j < 5; j++) {
curMask = curMask * 2 + alice[i - j];
curMask = curMask * 2 + bob[i - j];
}
if (maskToIdx[curMask] > 0) {
int cycleLen = i - maskToIdx[curMask];
int fastForward = max(0, (n - i) / cycleLen - 2);
n -= fastForward * cycleLen;
} else {
maskToIdx[curMask] = i;
}
}
}
return (alice[n] ? "Alice" : "Bob");
}
};
</int> < /int></map > </cmath> < /vector></string > </cstring> < /iomanip></iostream > </algorithm> < /unordered_map>
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package com.topcoder.tester.solutions.s33686163; /*end autogenerated code*/
import java.util.*;
public class PartisanGame {
static final int full = (1 << MAX_A) - 1;
static int enc(int maskA, int maskB) {
return maskA | (maskB << MAX_A);
}
static int decA(int data) {
return data & ((1 << MAX_A) - 1);
}
static int decB(int data) {
return data >> MAX_A;
}
static int getPos(int[] a) {
int pos = 0;
for (int i = 0; i < a.length; ++i) {
int x = a[i] - 1;
pos |= 1 << x;
}
return pos;
}
static int nextMask(int maskA, int maskB, int posB) {
int winB = (maskA & posB) != posB ? 1 : 0;
int nextMaskB = ((maskB << 1) | winB) & full;
return nextMaskB;
}
static int[] square(int[] a) {
int n = a.length;
int[] b = new int[n];
for (int i = 0; i < n; ++i)
b[i] = a[a[i]];
return b;
}
public static String getWinner(int n, int[] a, int[] b) {
int[] f = new int[1 << (2 * MAX_A)];
int posA = getPos(a);
int posB = getPos(b);
for (int maskA = 0; maskA < (1 << MAX_A); ++maskA) {
for (int maskB = 0; maskB < (1 << MAX_A); ++maskB) {
int cur = enc(maskA, maskB);
int nextMaskA = nextMask(maskB, maskA, posA);
int nextMaskB = nextMask(maskA, maskB, posB);
int next = enc(nextMaskA, nextMaskB);
f[cur] = next;
}
}
int maskA = 0;
int maskB = 0;
for (int i = 0; i < Math.min(MAX_A, n); ++i) {
int cur = (1 << Math.min(i + 1, MAX_A)) - 1;
int winA = (maskB & posA & cur) != (posA & cur) ? 1 : 0;
int winB = (maskA & posB & cur) != (posB & cur) ? 1 : 0;
maskA = (maskA << 1) | winA;
maskB = (maskB << 1) | winB;
}
int cur = enc(maskA, maskB);
n -= Math.min(MAX_A, n);
while (n > 0) {
if ((n & 1) == 1)
cur = f[cur];
f = square(f);
n >>= 1;
}
String ans = (decA(cur) & 1) == 1 ? "Alice" : "Bob";
return ans;
}
};
One can notice that strings in the collection can be obtained using following pseudocode:
1 2 3 4 5 6
L = 0, R = | s | -1, res[0...( | s | -1)](resulting string) from c = s[0] to s[ | s | -1] we can choose one of: 1. res[L++] = c 2. res[R--] = c add res to collection
Using this, we can calculate number of strings with given prefix using dp. Let dp[i][j] be the number of ways to match strings, given we have used i characters, and j characters have been added to the front. Now, we want to add the i-th character. If we want to add it to the left, it will go to position j in the string. Otherwise, if we add it to the right, it will go to position n - 1 - (i - j). We are allowed to add this character to the string if it matches the position specified by prefix (or the position lies out of bounds). Thus, we can use this logic to update our dp table to count the number of ways. See the code for more details on how the recurrence is updated.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.*;
public class KthStringAgain {
public static long count(String s, String p) {
int n = s.length();
int m = p.length();
long[][] d = new long[n + 1][n + 1];
d[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
int l = j;
int r = n - 1 - (i - j);
if (l >= m || s.charAt(i) == p.charAt(l))
d[i + 1][j + 1] += d[i][j];
if (r >= m || s.charAt(i) == p.charAt(r))
d[i + 1][j] += d[i][j];
}
}
long ans = 0;
for (int j = 0; j <= n; ++j)
ans += d[n][j];
return ans;
}
public static String getKth(String s, long k) {
--k;
int n = s.length();
String ans = "";
for (int i = 0; i < n; ++i) {
for (char c = 'a'; c <= 'z'; ++c) {
String p = ans + Character.toString(c);
long cnt = count(s, p);
if (cnt <= k) {
k -= cnt;
} else {
ans = ans + Character.toString(c);
break;
}
}
}
return ans;
}
};
FibonacciStringSum
Problem Details
One can notice and prove that for fixed a and b answer f(n, a, b) will be linear combination of f(n-1, a, b) … f(n-2 * (a + b + 1), a, b). Coefficients of linear reccurence can be found using gauss elimination or directly (say, using generating functions or other reasoning).
Alternatively, we can write a recurrence for the sum of x^a y^b over all strings of length n based on x^a’ y^b’ of all strings of length n-1 (using the fact that (x+1)^a is a linear combination of x^a, x^(a-1), … x^0). This gives O((ab)^3 * log(n)), which is too slow, unfortunately. However, we can use the fact that y = n-x, and expand (n-x)^b, so we only need to keep track of x^0, x^1, …, x^(a+b), so this gives a O((a+b)^3 * log(n)) solution.
Second solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class FibonacciStringSum {
public static int mod = 1000000007;
public int get(int n, int a, int b) {
int m = (a + b + 1);
long[][] comb = new long[2 * m][2 * m];
for (int i = 0; i < comb.length; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++) {
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
}
}
long[][] mat = new long[2 * m][2 * m];
// x is number of zeros.
// [0..m-1] -> x^i ends with 0
// [m..2*m-1] -> x^(i-m) ends with 1
for (int i = 0; i < 2 * m; i++) {
int end = i / m;
int curpow = i % m;
if (end == 0) {
for (int j = 0; j <= curpow; j++) {
mat[i][j] = (mat[i][j] + comb[curpow][j]) % mod;
mat[i][j + m] = (mat[i][j + m] + comb[curpow][j]) % mod;
}
} else {
mat[i][i - m]++;
}
}
mat = mat_exp(mat, n - 1);
long[] vec = new long[2 * m];
for (int i = 0; i < 2 * m; i++) {
int end = i / m;
int pow = i % m;
int n0 = (end == 0 ? 1 : 0), n1 = 1 - n0;
vec[i] = exp(n0, pow);
}
long[] xx = new long[2 * m];
for (int i = 0; i < 2 * m; i++) {
for (int j = 0; j < 2 * m; j++) {
xx[i] = (xx[i] + mat[i][j] * vec[j]) % mod;
}
}
long ans = 0;
for (int i = 0; i < 2 * m; i++) {
int pow = i % m;
long sign = (pow - a) % 2 == 0 ? 1 : (mod - 1);
if (pow < a || pow > a + b) continue;
long mm = exp(n, b - pow + a) * comb[b][pow - a] % mod * sign % mod;
ans = (ans + mm * xx[i]) % mod;
}
return (int) ans;
}
private static long exp(long b, long e) {
if (e == 0) return 1;
long r = 1;
while (e > 0) {
if (e % 2 == 1) r = r * b % mod;
b = b * b % mod;
e >>= 1;
}
return r;
}
private static long[][] mat_exp(long[][] A, int e) {
if (e == 0) {
long[][] ret = new long[A.length][A.length];
for (int i = 0; i < A.length; i++) ret[i][i] = 1;
return ret;
}
if (e == 1)
return A;
else if (e % 2 == 0) {
long[][] A1 = mat_exp(A, e / 2);
return matrix_mult(A1, A1);
} else
return matrix_mult(A, mat_exp(A, e - 1));
}
private static long[][] matrix_mult(long[][] A, long[][] B) {
long[][] C = new long[A.length][A.length];
for (int i = 0; i < A.length; i++)
for (int j = 0; j < A.length; j++)
for (int k = 0; k < A.length; k++)
C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % mod;
return C;
}
}
Solution by finding a linear recurrence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
public class FibonacciStringSum {
public static int add(int x, int y) {
x += y;
if (x >= mod)
x -= mod;
return x;
}
public static int sub(int x, int y) {
x -= y;
if (x < 0)
x += mod;
return x;
}
public static int mul(int x, int y) {
long p = (long) x * (long) y % mod;
return (int) p;
}
public static int binpow(int x, int to) {
int y = 1;
while (to > 0) {
if ((to & 1) == 1)
y = mul(x, y);
x = mul(x, x);
to >>= 1;
}
return y;
}
public static int inv(int x) {
assert(x != 0);
return binpow(x, mod - 2);
}
private static class Matrix {
int n;
int[][] a;
public Matrix(int size) {
n = size;
a = new int[n][n];
}
public Matrix one() {
Matrix ans = new Matrix(n);
for (int i = 0; i < n; ++i)
ans.a[i][i] = 1;
return ans;
}
public Matrix mul(Matrix other) {
Matrix ans = new Matrix(n);
for (int i = 0; i < n; ++i)
for (int k = 0; k < n; ++k)
for (int j = 0; j < n; ++j)
ans.a[i][j] = add(ans.a[i][j], FibonacciStringSum.mul(a[i][k], other.a[k][j]));
return ans;
}
}
public static Matrix binpow(Matrix x, int to) {
Matrix y = x.one();
while (to > 0) {
if ((to & 1) == 1)
y = y.mul(x);
x = x.mul(x);
to >>= 1;
}
return y;
}
public static int[] getCoefficients(int n) {
int[] a = new int[2 * n + 1];
a[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 2 * n; j >= 0; --j) {
int nw = sub(0, a[j]);
if (j >= 1)
nw = sub(nw, a[j - 1]);
if (j >= 2)
nw = add(nw, a[j - 2]);
a[j] = nw;
}
}
return a;
}
public static int[] getSequence(int cnt, int a, int b) {
int[] fact = new int[cnt + 1];
int[] ans = new int[cnt];
fact[0] = 1;
for (int i = 1; i < fact.length; ++i)
fact[i] = mul(i, fact[i - 1]);
BiFunction < integer, integer, = ""
integer = "" > binom = (Integer n, Integer k) - > {
if (n < 0 || k < 0 || n < k)
return 0;
int res = fact[n];
res = mul(res, inv(fact[k]));
res = mul(res, inv(fact[n - k]));
return res;
};
for (int n = 0; n < cnt; ++n) {
for (int k = 0; 2 * k - 1 <= n; ++k) {
int bon = binom.apply(n - k + 1, k);
bon = mul(bon, binpow(k, b));
bon = mul(bon, binpow(n - k, a));
ans[n] = add(ans[n], bon);
}
}
return ans;
}
public static int get(int n, int a, int b) {
int m = a + b + 1;
int[] c = getCoefficients(m);
int depth = c.length - 1;
Matrix A = new Matrix(depth);
for (int i = 0; i < depth; ++i)
A.a[0][i] = sub(0, c[depth - i - 1]);
for (int i = 1; i < depth; ++i)
A.a[i][i - 1] = 1;
A = binpow(A, n);
int[] seq = getSequence(depth, a, b);
int ans = 0;
for (int i = 0; i < depth; ++i)
ans = add(ans, mul(A.a[depth - 1][i], seq[depth - i - 1]));
return ans;
}
} <
/integer,>